#include <iostream>
#include <stdint.h>
#include <cassert>
#include <vector>
#include <stack>
#include <queue>
#include <utility>
using namespace std;

//Traverse thourgh a general tree in different ways:
//preorder, postorder and breadth first. Implementation doest 
//not depend on recursion

class TreeNode
{
	int info;
	TreeNode *nextSibling;
    public:
	vector<TreeNode*> children;
	TreeNode(int index): info(index), nextSibling(0) { }
	void addChild(int index) 
	{
	    TreeNode *node = new TreeNode(index);
	    if (children.size())
		children.back()->nextSibling = node;
	    children.push_back(node);
	}
	virtual ~TreeNode()
	{
	    vector<TreeNode*>::iterator it = children.begin();
	    while (it != children.end())
	    {
		delete *it;
		it++;
	    }
	}

	friend ostream& operator<<(ostream &os, const TreeNode &node);
	size_t childrenCount() const { return children.size();}
	TreeNode *getChild(unsigned int order) const { if (order < children.size()) return children[order]; return NULL; }
	TreeNode *getLastChild() const { return (children.empty())?NULL:children.back();}
	TreeNode *getSibling() const { return nextSibling; }
	void visit() const { cout << *this << " ";}

    class iterator;
    friend class iterator;
    //implement a iterator which traverse the tree in preorder manner
    class iterator : public std::iterator<std::forward_iterator_tag, TreeNode*>
    {
	TreeNode *tree;
	stack<TreeNode*> treeStack;
	public:
	iterator(TreeNode *t): tree(t) { treeStack.push(t);}
	bool operator!= (const iterator& x) const {
	    return tree != *x; 
	}

	iterator operator++(int)
	{
	    iterator tmp = *this;

	    TreeNode *curr = treeStack.top();
	    if (curr->childrenCount())
	    {
		tree = curr->getChild(0);
	    }
	    else
	    {
		treeStack.pop();
		while (!curr->getSibling())
		{
		    if (treeStack.empty()) break;
		    curr = treeStack.top();
		    treeStack.pop();
		}

		tree = curr->getSibling();
	    }

	    treeStack.push(tree);

	    return tmp;
	}

	std::iterator<std::forward_iterator_tag, TreeNode*>::value_type operator*() const
	{
	    return tree;
	}
    };

    iterator begin() { return iterator(this); }
    iterator end() { return iterator((TreeNode*)0); }
};

ostream& operator<<(ostream &os, const TreeNode &node)
{
    os << " (" << node.info << ") ";
    return os;
}

void preTreeVisitStack(const TreeNode *tree)
{
    if (!tree) return;
    stack<const TreeNode*> treeStack;
    tree->visit();
    treeStack.push(tree);

    while (!treeStack.empty())
    {
	const TreeNode *curr = treeStack.top();
	if (curr->childrenCount())
	{
	    //Put its first child into stack
	    TreeNode *child = curr->getChild(0);
	    child->visit();
	    treeStack.push(child);
	}
	else
	{
	    //Get out of stack
	    treeStack.pop();
	    while (!curr->getSibling() && treeStack.size())
	    {
		//pop out its ancestors with no more children left
		//(all children have been in stack once)
		curr = treeStack.top();
		treeStack.pop();
	    }

	    if (!treeStack.size()) break;
	    const TreeNode *sibling = curr->getSibling();
	    assert(sibling);
	    sibling->visit();
	    treeStack.push(sibling);
	}
    }

    cout << endl;
}

void postTreeVisitStack(const TreeNode *tree)
{
    //As it seems, postorder and preorder share the same stack in-out operation sequence
    if (!tree) return;
    stack<const TreeNode*> treeStack;
    treeStack.push(tree);

    while (!treeStack.empty())
    {
	const TreeNode *curr = treeStack.top();
	if (curr->childrenCount())
	{
	    TreeNode *child = curr->getChild(0);
	    treeStack.push(child);
	}
	else
	{
	    curr->visit();
	    treeStack.pop();
	    while (!curr->getSibling() && treeStack.size())
	    {
		curr = treeStack.top();
		curr->visit();
		treeStack.pop();
	    }

	    if (!treeStack.size()) break;
	    const TreeNode *sibling = curr->getSibling();
	    assert(sibling);
	    treeStack.push(sibling);
	}
    }

    cout << endl;
}

void breadthTreeVisitStack(const TreeNode *root)
{
    if (!root) return;
    queue<const TreeNode*> treeQueue;    
    treeQueue.push(root);

    while (!treeQueue.empty())
    {
	const TreeNode *tree = treeQueue.front();
	treeQueue.pop();
	tree->visit();
	for (vector<TreeNode*>::const_iterator it = tree->children.begin(); it != tree->children.end(); it++)
	{
	    treeQueue.push(*it);
	}
    }

    cout << endl;
}

int main(int argc, char* argv[])
{
    static int index = 1;
    TreeNode root(index++);
    root.addChild(index++);
    root.addChild(index++);
    root.addChild(index++);
    TreeNode *tree = root.getChild(0);
    tree->addChild(index++);
    tree->addChild(index++);
    tree = root.getChild(2);
    tree->addChild(index++);
    tree->addChild(index++);

    TreeNode::iterator it = root.begin(); 
    while (it != root.end())
    {
	(*it)->visit();
	it++;
    }

    cout << endl;

    preTreeVisitStack(&root);
    postTreeVisitStack(&root);
    breadthTreeVisitStack(&root);
    return 0;
}


